package com.cjm.algorithm.leetcode;

import java.util.*;

/**
 * 给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
 * <p>
 * 返回 已排序的字符串 。如果有多个答案，返回其中任何一个。
 */
public class FrequencySort451 {
    public static String frequencySort(String s) {

        char[] chars = s.toCharArray();
        Map<String, CharCount> map = new HashMap<>();

        for (int i = 0; i < chars.length; i++) {
            String aChar = String.valueOf(chars[i]);
            if (map.get(aChar) != null) {
                CharCount charCount = map.get(aChar);
                int times = charCount.getTimes();
                times ++;
                charCount.setTimes(times);
                continue;
            }
            CharCount temp = new CharCount(aChar, 1);
            map.put(aChar, temp);
        }
        Collection<CharCount> values = map.values();
        TreeSet<CharCount> count = new TreeSet<>(values);

        StringBuilder sb = new StringBuilder();
        while (!count.isEmpty()) {
            CharCount charCount = count.pollFirst();
            String item = charCount.getItem();
            int times = charCount.getTimes();
            for (int i1 = 0; i1 < times; i1++) {
                sb.append(item);
            }
        }

        return sb.toString();
    }

    static class CharCount implements Comparable<CharCount> {
        private String item;
        private int times;

        public CharCount() {
        }

        public CharCount(String item, int times) {
            this.item = item;
            this.times = times;
        }

        public String getItem() {
            return item;
        }

        public void setItem(String item) {
            this.item = item;
        }

        public int getTimes() {
            return times;
        }

        public void setTimes(int times) {
            this.times = times;
        }

        @Override
        public int compareTo(CharCount o) {
            return o.times - times == 0?o.getItem().compareTo(item) : o.times - times;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            CharCount charCount = (CharCount) o;
            return times == charCount.times && item.equals(charCount.item);
        }

        @Override
        public int hashCode() {
            return Objects.hash(item, times);
        }
    }

    public static void main(String[] args) {
        System.err.println(frequencySort("tree"));
        System.err.println(frequencySort("cccaaa"));
        System.err.println(frequencySort("Aabb"));
    }
}
